package hot100.logos31To40;

import hot100.datastruct.ListNode;

import java.util.PriorityQueue;

/**
 * @author logos
 * date 2025/7/13 12:07
 * @version v1.0
 * @Package hot100.logos31To40
 */
public class logos34 {
    /**
     * 34. 合并K个升序链表
     * https://leetcode.cn/problems/merge-k-sorted-lists/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution1 {
        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> x.val - y.val);
            for (ListNode node : lists) {
                if (node != null) {
                    heap.add(node);
                }
            }
            if (heap.isEmpty()) {
                return null;
            }
            ListNode head = heap.poll();
            ListNode cur = head;
            if (cur.next != null) {
                heap.add(cur.next);
            }
            while (!heap.isEmpty()) {
                ListNode nextNode = heap.poll();
                if (nextNode.next != null) {
                    heap.add(nextNode.next);
                }
                cur.next = nextNode;
                cur = nextNode;
            }
            return head;
        }
    }

    class Solution2 {
        public ListNode mergeKLists(ListNode[] lists) {
            return mergeKLists(lists, 0, lists.length - 1);
        }

        private ListNode mergeKLists(ListNode[] lists, int start, int end) {
            if (start > end) {
                return null;
            }
            if (start == end) {
                return lists[start];
            }
            int mid = start + (end - start) / 2;
            ListNode left = mergeKLists(lists, start, mid);
            ListNode right = mergeKLists(lists, mid + 1, end);
            return mergeTwoLists(left, right);
        }

        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode cur = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 != null ? list1 : list2;
            return dummy.next;
        }
    }

    class Solution3 {
        public ListNode mergeKLists(ListNode[] lists) {
            int n = lists.length;
            if (n == 0) {
                return null;
            }
            for (int step = 1; step < n; step *= 2) {
                for (int i = 0; i + step < n; i += step * 2) {
                    lists[i] = mergeTwoLists(lists[i], lists[i + step]);
                }
            }
            return lists[0];
        }

        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode();
            ListNode cur = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 != null ? list1 : list2;
            return dummy.next;
        }
    }


}
